// 基于无序缓存的实现，存储的结构采用了普通的对象，需要利用双向链表记录插入的顺序
// 其中存储的对象key值对应key，而value值对应相应的链表节点
// 双向链表也需要存储key值和value值

// 双向链表私有类（双向也是为了方便删除操作）
class LRUListNode<T extends ObjectIndexKey = number, U = number> {
    key: T;
    val: U;
    next: LRUListNode<T, U> | null;
    prev: LRUListNode<T, U> | null;
    constructor(key: T, value: U) {
        this.key = key;
        this.val = value;
        this.next = null;
        this.prev = null;
    }
}

// 无序缓存类
export class LRUCache<T extends ObjectIndexKey = number, U = number>{
    private cache: Partial<Record<T, LRUListNode<T, U>>>;
    private head: LRUListNode<T, U>;// 哨兵节点
    private tail: LRUListNode<T, U>;// 哨兵尾节点
    private readonly size: number;
    constructor(capacity: number) {
        this.size = capacity;
        this.cache = {};
        this.head = new LRUListNode(-1 as unknown as T, 'dh' as unknown as U);// dummyHead--->需要hack
        this.tail = new LRUListNode(-1 as unknown as T, 'dt' as unknown as U);// dummyTail--->需要hack
        this.head.next = this.tail;
        this.tail.prev = this.head;
    }
    // 将链表插到尾部方法
    private insertToTail(node: LRUListNode<T, U>): void {
        node.prev = this.tail.prev;
        this.tail.prev = node;
        if (node.prev == null) throw console.trace('意料之外的情况：');
        node.prev.next = node;
        node.next = this.tail;
    }
    // 取缓存方法
    get(key: T): -1 | U {
        const value: LRUListNode<T, U> | undefined = this.cache[key];
        if (typeof value === 'undefined') return -1;// 如果未查询到属性则直接返回
        // 先删除该节点，再将该节点接到尾部
        if (value.prev == null || value.prev.next == null || value.next == null || value.next.prev == null) {
            throw console.trace('意料之外的情况：');
        }
        value.prev.next = value.next;
        value.next.prev = value.prev;
        this.insertToTail(value);
        return value.val;
    }
    // 添加缓存
    put(key: T, value: U): void {
        // 直接调用这边的get方法，如果存在，它会在get内部被移动到尾巴，不用再移动一遍,直接修改值即可
        const node: LRUListNode<T, U> | undefined = this.cache[key];
        if (this.get(key) !== -1 && node) {
            node.val = value;
            return;
        }
        // 若不存在，new一个出来,如果超出容量，把头去掉
        const newNode = new LRUListNode(key, value);
        this.cache[key] = newNode;
        this.insertToTail(newNode);
        if (!this.head.next || !this.head.next.next) throw console.trace('意料之外的情况：');
        if (Object.keys(this.cache).length > this.size) {
            // 删除存储对象上的对应链表节点
            delete this.cache[this.head.next.key];
            this.head.next = this.head.next.next;
            this.head.next.prev = this.head;
        }
    }
}


// 测试用例
const cache = new LRUCache(3);
cache.put(1, 1);
cache.put(2, 2);
cache.put(3, 3);
cache.put(4, 4);
cache.get(4);
cache.get(3);
cache.get(2);
cache.get(1);
cache.put(5, 5);
cache.get(1);
cache.get(2);
cache.get(3);
cache.get(4);
cache.get(5);

